#include "BSP.h"
#include <vector>
#include "Scaler.h"
using namespace std;

void sRectangle::operator()(int aX1, int aY1, int aX2, int aY2){
	x1 = aX1;
	y1 = aY1;
	x2 = aX2;
	y2 = aY2;
	occupied = false;
}

BSP_Node::BSP_Node(){
	_rect(0,0,0,0);
	_parent = NULL;
	_left = NULL;
	_right = NULL;
}

BSP_Node::BSP_Node(sRectangle aRect){
	_rect = aRect;
	_parent = NULL;
	_left = NULL;
	_right = NULL;
}

BSP_Node::BSP_Node(sRectangle aRect, BSP_Node* aParent){
	_rect = aRect;
	_parent = aParent;
	_left = NULL;
	_right = NULL;
}

bool BSP_Node::separate(){

	float percPos = float(rand()%51+25);
	bool Vcut = true;
	if(_rect.y2 - _rect.y1 > _rect.x2 - _rect.x1) Vcut = false;

	sRectangle left, right;
	if(Vcut){ // V
		Scaler s(float(0),float(100),float(_rect.x1),float(_rect.x2));
		int pos = int(s.scale(percPos));
		if(pos - _rect.x1 < 4 || _rect.x2 - pos < 4) return false;
		left(_rect.x1, _rect.y1, pos, _rect.y2);
		right(pos, _rect.y1, _rect.x2, _rect.y2);
	}
	else{ // H
		Scaler s(float(0),float(100),float(_rect.y1),float(_rect.y2));
		int pos = int(s.scale(percPos));
		if(pos - _rect.y1 < 4 || _rect.y2 - pos < 4) return false;
		left(_rect.x1, _rect.y1, _rect.x2, pos);
		right(_rect.x1, pos, _rect.x2, _rect.y2);
	}

	BSP_Node* leftNode = new BSP_Node(left, this);
	BSP_Node* rightNode = new BSP_Node(right, this);
	_left = leftNode;
	_right = rightNode;

	return true;
}

BSP::BSP():_root(NULL){};

BSP::~BSP(){ if(_root != NULL) destroyTree(_root);};

vector<sRectangle> BSP::produce(int aX1, int aY1, int aX2, int aY2, int aLevels){
	sRectangle begin = {aX1, aY1, aX2, aY2};
	return produce(begin,aLevels);
}

vector<sRectangle> BSP::produce(sRectangle aRect, int aLevels){
	_root = new BSP_Node(aRect);
	vector<sRectangle> rectRet;

	for(int i=0; i<=aLevels; i++){
		_leafs.clear();
		findLeafs(_root);
		for(unsigned int l=0; l<_leafs.size(); l++){
			if(i != aLevels) _leafs[l]->separate(); // normal situation, separating tree node into two
			else rectRet.push_back(_leafs[l]->_rect); // finishing algorithm, adding rectangles to the return vector
		}
	}

	return rectRet;
}

void BSP::findLeafs(BSP_Node* aNode){
	if(aNode->isLeaf()) _leafs.push_back(aNode);
	else{
		findLeafs(aNode->_left);
		findLeafs(aNode->_right);
	}
}

void BSP::destroyTree(BSP_Node* aNode){
	if(aNode->_left != NULL) destroyTree(aNode->_left);
	if(aNode->_right != NULL) destroyTree(aNode->_right);
	delete aNode;
}